package bintree.LeetCode;
//572. 另一棵树的子树

/**
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
 * 如果存在，返回 true ；否则，返回 false
 */

public class Num572_isSubtree {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //1.边界
        if(root == null && subRoot == null){
            //都是空树，认为是相同的。
            return true;
        }
        //2.走到这说明两个树不会全为空，至少有一个不为空
        if(root == null || subRoot == null){
            //如果p == null，那么q就不可能再为null，不然就走上面那条语句了
            return false;
        }

        //都不为空的情况
        //从根开始相同的树、左子树里面包含相同树、右子树里面包含相同树；
        //只要有一个条件满足就成立！
        return isSameTree(root, subRoot) ||
                isSubtree(root.left, subRoot) ||
                isSubtree(root.right, subRoot);
    }     //注释：如果跟节点相同，就用isSameTree方法判断是否是相同树。不同就交给子方法继续去判断
    //判断是否为相同树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.边界
        if(p == null && q == null){
            //都是空树，认为是相同的。
            return true;
        }
        //2.走到这说明两个树不会全为空，至少有一个不为空
        if(p == null || q == null){
            //如果p == null，那么q就不可能再为null，不然就走上面那条语句了
            return false;
        }

        //都不为空的情况

        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

}
